#define LETTER_NUM 26
#define MAX_LENGTH 100001

// 降序 比较函数
int cmp_down(const void *a, const void *b)
{
    return (*(int *)b - *(int *)a);
}

int minDeletions(char *s)
{
    int i;
    int hash[LETTER_NUM] = {0}; // 统计字母出现个数
    int flag[MAX_LENGTH] = {0}; // 标记是否已经出现过，出现flag = 1
    int str_len = strlen(s);
    int min_delete = 0;

    for (i = 0; i < str_len; i++) {
        hash[s[i] - 'a']++;
    }
    qsort(hash, LETTER_NUM, sizeof(int), cmp_down);

    for (i = 0; i < LETTER_NUM; i++) {
        // 如果出现次数为0，停止循环
        if (hash[i] == 0) {
            break;
        }

        // 如果没有出现过，标记为1
        if (flag[hash[i]] == 0) {
            flag[hash[i]] = 1;
        } else {
            while (1) {
                min_delete++;
                hash[i]--;
                // 如果减小到数字0，跳出本次循环
                if (hash[i] == 0) {
                    break;
                }
                // 如果减小到没有出现，标记为1，跳出本次循环
                if (flag[hash[i]] == 0) {
                    flag[hash[i]] = 1;
                    break;
                }
            }
        }
    }

    return min_delete;
}

